public class Solution {

    public static int GetUglyNumber_Solution(int index) {
        if(index<=0)
            return 0;
        int[] ugly = new int[index];
        if(index>=1 && index<=5){
            for(int i=0;i<index;i++){
                ugly[i] = i+1;
            }
        }
        else{
            for(int i=0;i<5;i++){
                ugly[i] = i+1;
            }
            int i=4;
            int t2=0;//当前的乘以2的丑数位置
            int t3=0;
            int t5=0;
            int m2=0,m3=0,m5=0;//乘以2得到的最新丑数
            while(i+1<index){
                while(t2<index && m2<=ugly[i]){
                    m2 = ugly[t2]*2;
                    t2 +=1;
                }
                while(t3<index && m3<=ugly[i]){
                    m3 = ugly[t3]*3;
                    t3 +=1;
                }
                while(t5<index-1 && m5<=ugly[i]){
                    m5 = ugly[t5]*5;
                    t5 +=1;
                }
                //从m2,m3,m5中找到最小的丑数，对应t+1
                if(m2<m3){
                    if(m2<m5){
                        ugly[++i] = m2;//m2最小
                    }else{
                        ugly[++i] = m5;
                    }
                }else{
                    if(m3<m5){
                        ugly[++i] = m3;
                    }else{
                        ugly[++i] = m5;
                    }
                }
            }
        }
        return ugly[index-1];

    }
    public static void main(String args[]){
        int k=8;
        int b = GetUglyNumber_Solution(k);
        System.out.println(b);
    }

}

